广度优先遍历ＢＦＳ

思考步骤

求解目标

求解路径长度，还是路径？

1. 如果是求路径长度，则状态里面要存路径长度（或双队列+一个全局变量）
2. 如果是求路径本身或动作序列
   1. 要用一棵树存储宽搜过程中的路径
   2. 是否可以预估状态个数的上限？能够预估状态总数，则开一个大数组，用树的双亲表示法；如果不能预估状态总数，则要使用一棵通用的树。这一步也是第4步的必要不充分条件

状态表示

即一个状态需要存储哪些些必要的数据，才能够完整提供如何扩展到下一步状态的所有信息。一般记录当前位置或整体局面。

状态扩展

这一步跟第2步相关。状态里记录的数据不同，扩展方法就不同。对于固定不变的数据结构（一般题目直接给出，作为输入数据），如二叉树，图等，扩展方法很简单，直接往下一层走，对于隐式图，要先在第1步里想清楚状态所带的数据，想清楚了这点，那如何扩展就很简单了。

判断状态重复

如果状态转换图是一颗树，则永远不会出现回路，不需要判重；如果状态转换图是一个图（这时候是一个图上的BFS），则需要判重。

1. 如果是求最短路径长度或一条路径，则只需要让“点”（即状态）不重复出现，即可保证不出现回路
2. 如果是求所有路径，注意此时，状态转换图是DAG，即允许两个父节点指向同一个子节点。具体实现时，每个节点要“延迟”加入到已访问集合visited，要等一层全部访问完后，再加入到visited集合。
3. 具体实现
   • 状态是否存在完美哈希方案？即将状态一一映射到整数，互相之间不会冲突。
   • 如果不存在，则需要使用通用的哈希表（自己实现或用标准库，例如unordered_set）来判重；自己实现哈希表的话，如果能够预估状态个数的上限，则可以开两个数组，head和next，表示哈希表。
   • 如果存在，则可以开一个大布尔数组，来判重，且此时可以精确计算出状态总数，而不仅仅是预估上限

代码模板

广搜ＢＦＳ需要

一个队列，用于一层一层扩展；

一个hashset，用于判重；

一棵树（只求长度时不需要），用于存储整棵树。

对于队列，可以用queue，也可以把vector当做队列使用。当求长度时，有两种做法：

1. 只用一个队列，但在状态结构体state_t里增加一个整数字段level，表示当前所在的层次，当碰到目标状态，直接输出level即可。这个方案，可以很容易的变成A*算法，把queue替换为priority_queue即可。
2. 用两个队列，current, next，分别表示当前层次和下一层，另设一个全局整数level，表示层数（也即路径长度），当碰到目标状态，输出level即可。这个方案，状态里可以不存路径长度，只需全局设置一个整数level，比较节省内存；

例题

wordladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

• Only one letter can be changed at a time
• Each intermediate word must exist in the dictionary

for example

start = “hit”
end = “cog”
dict = [“hot”,”dot”,”dog”,”lot”,”log”]

As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, return its length 5

Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

#include<iostream>
#include<unordered_set>
#include<string>
#include<vector>
#include<queue>
#include<set>

using namespace std;
//定义状态
typedef struct state {
	string word;
	int level;
	state(string s, int lvl) :word(s), level(lvl) {}
}state;
//在字典中存在且与目标有相同元素则是可用的
bool IsValid(string s, const string endWord, unordered_set<string> dict) {
	if (dict.find(s) == dict.end())return false;
	for (int i = 0; i<s.size(); ++i) {
		if (s[i] == endWord[i])return true;
	}
	return false;
}

void swap(char &a, char &b) {
	char tmp = a;
	a = b;
	b = tmp;
}

int lengthofladder(const string beginWord, const string endWord, unordered_set<string> dict) {
	if (beginWord.size() != endWord.size())return 0;
	if (beginWord.size() == 0 || dict.empty())return 0;

	int len = beginWord.size();
	int minlength = INT_MAX;

	queue<state> nextstate;//表示状态队列
	set<string> visited; //表示已经转换过的词语
	state head(beginWord, 1);
	nextstate.push(head);
	//state *node=nullptr;

	while (!nextstate.empty()) {
		state node = nextstate.front();
		cout << node.word << endl;
		visited.insert(node.word);
		nextstate.pop();
		string str = node.word;
		for (int i = 0; i<str.size(); i++) {
			for (char c = 'a'; c <= 'z'; c++) {
				if (c == str[i])continue;
				swap(c, str[i]);
				if (visited.find(str) != visited.end())continue;
				if (str == endWord) { //要求最短的路径
					return (minlength > node.level + 1 ? node.level + 1 : minlength);
				}
				if (IsValid(str, endWord, dict)) {
					state newWord(str, node.level + 1);
					nextstate.push(newWord);
				}
				swap(c, str[i]);

			}
		}
	}
	return 0;
}

int main() {
	string begin = "hit";
	string end = "cog";
	vector<string> vec = { "hot","dot","dog","sit","lot","log" ,"cog"};
	unordered_set<string> d(vec.begin(), vec.end());
	int x = lengthofladder(begin, end, d);
	cout << x << endl;
	return 0;
}

注意

set没有push方法，添加元素只有insert方法。

queue没有insert方法，需要push。也没有top方法，只有front方法和back方法。

深度优先遍历ＤＦＳ

适用场景

求解目标：多阶段存在性问题。必须要走到最深（例如对于树，必须要走到叶子节点）才能得到一个解，这种情况适合用深搜。

思考步骤

１，问题类型

深搜最常见的三个问题，求可行解的总数，求一个可行解，求所有可行解。
如果是路径条数，则不需要存储路径。
如果是求路径本身，则要用一个数组path[]存储路径。跟宽搜不同，宽搜虽然最终求的也是一条路径，但是需要存储扩展过程中的所有路径，在没找到答案之前所有路径都不能放弃；而深搜，在搜索过程中始终只有一条路径，因此用一个数组就足够了

２，求解个数

只要求一个解，还是要求所有解？如果只要求一个解，那找到一个就可以返回；如果要求所有解，找到了一个后，还要继续扩展，直到遍历完。广搜一般只要求一个解，因而不需要考虑这个问题

３，状态表示

如何表示状态？即一个状态需要存储哪些些必要的数据，才能够完整提供如何扩展到下一步状态的所有信息。跟广搜不同，深搜的惯用写法，不是把数据记录在状态struct里，而是添加函数参数（有时为了节省递归堆栈，用全局变量），struct里的字段与函数参数一一对应。

４，扩展状态

如何扩展状态？这一步跟上一步相关。状态里记录的数据不同，扩展方法就不同。对于固定不变的数据结构（一般题目直接给出，作为输入数据），如二叉树，图等，扩展方法很简单，直接往下一层走，对于隐式图，要先在第1步里想清楚状态所带的数据，想清楚了这点，那如何扩展就很简单了

５，终止条件

终止条件是什么？终止条件是指到了不能扩展的末端节点。对于树，是叶子节点，对于图或隐式图，是出度为0的节点。

６，收敛条件

收敛条件是什么？收敛条件是指找到了一个合法解的时刻。如果是正向深搜（父状态处理完了才进行递归，即父状态不依赖子状态，递归语句一定是在最后，尾递归），则是指是否达到目标状态；如果是逆向深搜（处理父状态时需要先知道子状态的结果，此时递归语句不在最后），则是指是否到达初始状态。

为了判断是否到了收敛条件，要在函数接口里用一个参数记录当前的位置（或距离目标还有多远）。如果是求一个解，直接返回这个解；如果是求所有解，要在这里收集解，即把第一步中表示路径的数组path[]复制到解集合里。

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/**
 * dfs模板.
 * @param[in] input 输入数据指针
 * @param[out] path 当前路径，也是中间结果
 * @param[out] result 存放最终结果
 * @param[inout] cur or gap 标记当前位置或距离目标的距离
 * @return 路径长度，如果是求路径本身，则不需要返回长度
 */
void DFS(type &input, type &path, type &result, int cur or gap) {
    if (数据非法) return 0;   // 终止条件
    if (cur == input.size()) { // 收敛条件
    // if (gap == 0) {
        将path放入result
    }

    if (可以剪枝) return;

    for(...) { // 执行所有可能的扩展动作
        执行动作，修改path
        dfs(input, step + 1 or gap--, result);
        恢复path
    }
}

例题

累加数

累加数是一个字符串，组成它的数字可以形成累加序列。

一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。

给定一个只包含数字 ‘0’-‘9’ 的字符串，编写一个算法来判断给定输入是否是累加数。

说明: 累加序列里的数不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况

输入: “112358”
输出: true
解释: 累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

输入: “199100199”
输出: true
解释: 累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

bool isAdditiveNumber(string num) {
		int n = num.size();
		if (n <= 2)return false;
		for (int i = 1; i < n; ++i) {
			for (int j = 1; j < n - i; ++j) {
				string str1 = num.substr(0, i);
				string str2 = num.substr(i, j);
				if ((str1.size() > 1 && str1[0] == '0') || (str2.size() > 1 && str2[0] == '0'))continue;
				long long num1 = atoll(str1.c_str());//substr(开始位置，长度)
				long long num2 = atoll(str2.c_str());
				long long num3 = num1 + num2;
				string num3_str = to_string(num3);
				string newstring = str1 + str2 + num3_str;
				while (newstring.size() < n) {
					num1 = num2;
					num2 = num3;
					num3 = num1 + num2;
					newstring += to_string(num3);
				}

				if (newstring == num)return true;
			}
		}
		return false;
	}

注意

回溯法 = 深搜 + 剪枝。一般大家用深搜时，或多或少会剪枝，因此深搜与回溯法没有什么不同，可以在它们之间画上一个等号。

深搜一般用递归(recursion)来实现.